// 给定一个非负整数数组，你最初位于数组的第一个位置。
// 数组中的每个元素代表你在该位置可以跳跃的最大长度。
// 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
// 思路1， 贪心
// 统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖
// 如果到了移动位置等于最大覆盖且没有到达终点，必须再走一步来增加覆盖范围
// 对于索引到达最远覆盖距离，如果是集合终点，不需要加1，不是的话，继续加1，
// 这个可以通过`i < nums.length - 1`简化，当下标指向`nums.length - 2`,在走一步，肯定可以到达终点，否则，已经覆盖到终点了
function jump(nums) {
    let curDistance = 0
    let nextDistance = 0
    let ans = 0
    for (let i = 0; i < nums.length - 1; i++) {
        nextDistance = Math.max(nextDistance, nums[i] + i)
        if (i === curDistance) {
            ans++
            curDistance = nextDistance
        }        
    }
    return ans
}

console.log(jump([2,3,1,1,4]))

// 思路2，动态规划
// dp[i]表示为，跳到下标i所需要的的最小跳跃次数
// 状态转移方程
// 1. 当前位置i，如果之前的位置j能够跳到位置i需要满足：位置j加上位置j所能跳到最远长度要大于等于i，即j + nums[j] >= i
// 2. 跳到下标i所需要的最小跳跃次数则等于满足上述要求的位置j中最小跳跃次数加1，即dp[i] = min(dp[i], dp[j] + 1)

function jump2(nums) {
    let dp = new Array(nums.length).fill(Infinity)
    dp[0] = 0
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (j + nums[j] >= i) {
                dp[i] = Math.min(dp[i], dp[j] + 1)
            }
        }        
    }
    return dp[nums.length - 1]
}

console.log(jump2([2,3,1,1,4]))